package com.skh.array;

import java.util.Arrays;

/**
 * created by skh on 2019/3/6
 */
public class SortColors {

	/*
	给定一个数组，其中有n个对象分别为红色、白色或蓝色，对它们进行排序，使相同颜色的对象相邻，颜色的顺序为红色、白色和蓝色。
	在这里，我们将使用整数0,1和2分别表示红色、白色和蓝色。
	注意:
	对于这个问题，您不应该使用库的排序函数。
	单击此处显示后续操作。
	跟进:
	一个相当直接的解决方案是使用计数排序的双通道算法。
	首先，遍历数组中0、1和2的计数，然后用总数为0、1和2的数组覆盖数组。
	你能想出只使用常数空间的一遍算法吗?
	 */



	public void sortColors(int[] A) {

		tongpaixu(A);
	}






	//桶排序
	private void tongpaixu(int[] A) {

		int[] count = new int[3];
		//统计1,2,3出现的次数
		for (int num : A) {
			count[num]++;
		}

		//根据count,新建数组
		int index = 0;
		for (int i = 0; i < count[0]; i++) {
			A[index++] = 0;
		}
		for (int i = 0; i < count[1]; i++) {
			A[index++] = 1;
		}
		for (int i = 0; i < count[2]; i++) {
			A[index++] = 2;
		}
	}


}
